15.1 Введение в онлайн-обучение

О чём раздел про онлайн-обучение, кому и зачем его читать?

Во многих случаях обучение ML-модели ― это однократный процесс, после которого она не меняется и только используется для предсказания. А что, если к нам постоянно поступает новая информация и мы должны её учитывать? Тогда модель должна уметь обновляться при поступлении нового объекта или батча объектов. Грубо говоря, этим и занимается онлайн-оптимизация. Можно заметить, что обновление модели на батче объектов проходит и в процессе стохастической оптимизации, ― и это сходство не случайно.

Оказывается, что все известные вам методы стохастической оптимизации первого порядка ― такие как SGD, AdaGrad, Adam, AMSgrad и другие ― являются в первую очередь алгоритмами онлайн-обучения. Чтобы в этом убедиться, достаточно открыть эти статьи и увидеть, для какой задачи выводятся гарантии на сходимость. Постановка задачи онлайн-обучения является одновременно математически простой и очень общей, соединяя три больших темы:

  1. «Классическое» онлайн обучение.
  2. Стохастическую оптимизацию на фиксированном датасете. Мы покажем, что любой алгоритм онлайн обучения можно переформулировать, как алгоритм стохастической оптимизации; при этом из гарантий на сходимость, полученных для онлайн обучения, автоматически будет следовать сходимость на фиксированном датасете.
  3. Adversarial обучение.

Данный текст является в первую очередь систематизирующим. Мы постараемся достичь следующих целей:

  1. Подведем единую математическую базу, необходимую для вдумчивого чтения статей по оптимизации. Это будет полезно ML-теоретикам.
  2. Покажем, как исторически развивались методы оптимизации, как из одного метода получался другой, какие проблемы они решали и ― главное ― актуальны ли эти проблемы сейчас.
  3. Разберём все «именные» методы оптимизации на набор базовых концепций и покажем, как вы можете самостоятельно их сочетать, создавая оптимальный метод для решения своей задачи. Спойлер: базовых концепций намного меньше, чем наименований методов. Эти знания будут полезны ML-инженерам.
  4. Пройдемся по относительно нишевым темам, таким как разреженные методы регуляризации L1L_1 и L1/2L_{1/2}, и рассмотрим наилучшие методы оптимизации для них. Такие методы невозможно получить в стандартной постановке стохастической оптимизации. Эти знания будут полезны ML-инженерам, занимающимся рекомендательными системами.

В параграфе «Введение в онлайн-обучение», которую вы читаете сейчас, вы познакомитесь с общей постановкой задачи онлайн-обучения, а также с семейством алгоритмов Follow the Regularized Leader (FTRL), которое включает в себя все методы первого порядка. Кроме того, вы узнаете, как сводить задачи стохастической оптимизации к задачам онлайн-обучения и увидите, что этот переход позволяет строить более эффективные методы стохастической оптимизации, особенно для разреженных регуляризаторов вроде L1L_1.

В параграфе «Адаптивный FTRL» вы узнаете, как улучшить сходимость алгоритмов стохастической оптимизации с помощью регуляризаторов и каковы гарантии сходимости для регуляризованных задач. Это позволит вывести AdaGrad как наилучший адаптивный метод для онлайн-оптимизации.

В параграфе «Регуляризация в онлайн-обучении» мы снова поговорим о регуляризации, но на этот раз речь пойдёт о регуляризаторах, которые накладывают на решение определённые органичения, например, разреженность. Вы сможете с новой стороны взглянуть на разреживающие свойства L1L_1-регуляризаторов. Кроме того, мы получим не достижимые с помощью обычных SGD/AdaGrad результаты для разреженных L1L_1 и L1/2L_{1/2} регуляризаторов.

В параграфе «Стохастическая оптимизация в Deep Learning» мы перейдём к методам оптимизации в глубоких нейросетях. Вас ждёт краткий исторический обзор и мотивация появления двух важных модификаций AdaGrad ― Adam и RMSprop. Мы покажем, что эти методы ломаются вокруг критических точек, и поговорим о том, как починить это и достичь более точной сходимости (этого эффекта можно достичь либо прямой модификацией алгоритмов (AMSgrad и RAdam), либо косвенно с помощью Learning Rate Scheduler'ов).

В конце параграфа мы соберём воедино все рассмотренные концепции и покажем, как можно комбинировать лучшее из разных методов оптимизации в один новый метод.

Оглавление

Часть 1. Введение
Часть 2. Адаптивные методы оптимизации
Часть 3. Продвинутые методы регуляризации
Часть 4. Методы оптимизации в Deep Learning
Часть 5. Заключение

Постановка задачи

Литература. Отсюда и далее, пока явно не скажем о переходе на другие источники информации, используется материал из книги Shai Shalev-Shwartz Online Learning and Online
Convex Optimization

Онлайн-обучение ― это процесс предсказания ответов на последовательность вопросов с учётом знания (возможно, неполного) о предыдущих правильных ответах.

Представим себе следующую игру (назовём её игра (1)). На каждом раунде игры tt мы:

  1. Получаем xtx_t ― частичную информацию о текущем «вопросе»;
  2. Выбираем модель wtw_t, которой будем делать прогноз;
  3. Прогнозируем pt(wt,xt)p_t(w_t, x_t);
  4. Получаем истинный ответ yty_t;
  5. Получаем обратную связь-лосс l(pt,yt)l(p_t, y_t). Лоссы обычно имеют семантику функции ошибки: больше ― хуже, меньше ― лучше.

Цель любого алгоритма онлайн обучения ― минимизация суммарной ошибки прогнозов Loss(T)=t=1Tl(pt,yt)Loss(T) = \sum\limits_{t=1}^Tl(p_t, y_t) для любого количества раундов TT.

Пока рассмотрим интуитивный пример: линейная регрессия (обозначения взяты из параграфа про линейные модели). Пусть у нас уже сыграны раунды 1,,t11,\ldots,t-1 и есть выборка данных x1,,xt1x_1,\ldots,x_{t-1} и ответов y1,,yt1y_1,\ldots,y_{t-1}.

  1. Получаем новый xtx_t. В данном случае просто получаем и пока не используем;
  2. Выбираем модель wtw_t, которая наилучшим образом объясняет всю предыдущую имеющуюся выборку x1..tx_{1..t} (алгоритм обучения можем выбирать любой, какой нам нравится);
  3. Прогнозируем pt=<wt,xt>p_t = <w_t, x_t>;
  4. Получаем правильный ответ yty_t;
  5. Считаем loss (ytpt)2(y_t - p_t)^2;

Действуя таким образом, мы делаем интуитивное предположение, что ответы yty_t как-то зависят от наших xtx_t и что эту зависимость мы можем выучить из предыдущей выборки, улучшив прогноз на новых объектах.

Предположения

Теория онлайн обучения выгодно отличается от классической теории статистического обучения довольно расслабленными и гораздо более простыми (с точки зрения математических формулировок) условиями. Мы не делаем предположений о некой статистической зависимости между xtx_t, yty_t. Зависимость может быть детерминированной, стохастической или даже adversarial:

  1. Детерминированная: в самом начала игры делается выбор детерминированной зависимости xtytx_t \rightarrow y_t
  2. Стохастическая: xtx_t может быть реализациями случайной величины, зависящей от yty_t
  3. Adversarial: мы играем против активного противника, который может на каждом раунде игры по своему усмотрению менять зависимость xtytx_t \rightarrow y_t и/или подбирать l(pt,yt)l(p_t, y_t), имея на руках в том числе текущий ответ yty_t, не доступный алгоритму онлайн-обучения

Adversarial постановка включает в себя все остальные как частные случаи, так что сразу будем строить теорию для наиболее общего случая.

Поведение алгоритма на шаге T

Начнем с введения метрики качества алгоритма на некотором раунде игры TT, а затем расширим ее на все раунды игры.

Если у противника нет никаких ограничений, то противник всегда выигрывает. Поскольку l(pt,yt)l(p_t, y_t) выбирается после нашего прогноза, он может выбрать любую функцию с сколь угодно большим штрафом.

Чтобы такого не случалось, мы предположим, что все ответы на шаге TT должны быть сгенерированы некоторым отображением h:XY,hHh^*: X\rightarrow Y, h^* \in H, где HH ― пространство возможных решений, известное и онлайн-алгоритму, и противнику.

С учетом введенного ограничения на поведение противника, введем понятие regret:

RegretT(h)=t=1Tl(pt,yt)t=1Tl(h(xt),yt)Regret_T(h) = \sum\limits_{t=1}^T l(p_t, y_t) - \sum\limits_{t=1}^Tl(h(x_t), y_t)

Regret ― это метрика того, насколько онлайн алгоритм работает хуже, чем некоторая фиксированная модель-бейзлайн h (regret переводится как «сожаление»: насколько мы пожалели о том, что взяли онлайн алгоритм, а не модель h). Поскольку мы работаем в adversarial случае, то логично сравнивать наш онлайн алгоритм с сильнейшим возможным противником, а именно: противник всегда выбирает не «некоторую», а наилучшую модель-бейзлайн hHh^* \in H:

maxRegret(T)=maxhH[t=1Tl(pt,yt)t=1Tl(h(xt),yt)]maxRegret(T) = \max\limits_{h^* \in H}\left[ \sum\limits_{t=1}^T l(p_t, y_t) - \sum\limits_{t=1}^Tl(h^*(x_t), y_t)\right]

Поведение алгоритма на всей последовательности раундов игры

Вспомним, что вообще-то мы играем игру с бесконечным числом раундов. В таком случае, естественно будет анализировать поведение ряда maxRegret(T),TN,TmaxRegret(T), T \in \mathbb{N}, T \rightarrow \infty. Здесь хочется еще раз подчеркнуть, в чем заключается adversarial поведение: на каждом шаге t maxRegret будет иметь свою наилучшую модель hth^*_t в бейзлайне:

maxRegret(T1)=maxhHt=1T1l(pt,yt)t=1T1l(h(xt),yt)=t=1T1l(pt,yt)t=1T1l(hT1(xt),yt)maxRegret(\color{#348FEA}{T_1}) = \max\limits_{h^* \in H} \sum\limits_{t=1}^{\color{#348FEA}{T_1}} l(p_t, y_t) - \sum\limits_{t=1}^{\color{#348FEA}{T_1}}l(h^*(x_t), y_t) = \sum\limits_{t=1}^{\color{#348FEA}{T_1}} l(p_t, y_t) - \sum\limits_{t=1}^{\color{#348FEA}{T_1}}l(h^*_{\color{#348FEA}{T_1}}(x_t), y_t)

maxRegret(T2)=maxhHt=1T2l(pt,yt)t=1T2l(h(xt),yt)=t=1T2l(pt,yt)t=1T2l(hT2(xt),yt)maxRegret(\color{#E06A27}{T_2}) = \max\limits_{h^* \in H} \sum\limits_{t=1}^{\color{#E06A27}{T_2}} l(p_t, y_t) - \sum\limits_{t=1}^{\color{#E06A27}{T_2}}l(h^*(x_t), y_t) = \sum\limits_{t=1}^{\color{#E06A27}{T_2}} l(p_t, y_t) - \sum\limits_{t=1}^{\color{#E06A27}{T_2}}l(h^*_{\color{#E06A27}{T_2}}(x_t), y_t)

Качество онлайн алгоритма на протяжении всей игры

Когда мы говорим про adversarial setting и игру с противником, мы хотим не просто как-то минимизировать кумулятивный Loss(T)=t=1Tl(pt,yt)Loss(T) = \sum\limits_{t=1}^Tl(p_t, y_t), но еще и хотим быть не хуже нашего противника. Потребуем, чтобы

limT1TmaxRegret(T)=0\lim\limits_{T \rightarrow \infty} \frac{1}{T}maxRegret(T) = 0

Такое условие означает, что regret должен расти медленнее чем линейно (в таком случае говорят, что алгоритм имеет сублинейный regret).

Сублинейности бывают разные. Так, RegretTRegret_T может быть ограничен сверху рядом с асимптотикой T\sqrt{T} или же рядом с асимптотикой logT\log{T}

Асимптотика logT\log{T}, очевидно, приводит к намного лучшей сходимости. Но достичь этого не всегда возможно. Стандартной асимптотикой regret в большинстве используемых на практике алгоритмов является T\sqrt{T}, для этой асимптотики условия на задачу наименее жесткие. Все рассматриваемые нами ниже алгоритмы будут иметь асимптотику T\sqrt{T} и отличаться в основном константами в оценках (но, конечно, отличия в константах при оценке Regret часто приводят к существенно разному поведению на практике). Любые более мощные асимптотики требуют условий, которые крайне редко выполняются в практических задачах

Online to batch conversion

В данном обзоре мы будем анализировать методы, которые гораздо чаще используются для оптимизации в классической постановке: есть фиксированный датасет (xi,yi)i=1N(x_i, y_i)_{i=1}^N, модель pw(x)p_w(x) с обучаемыми параметрами ww и функция потерь ff, задача ― найти минимум функции

1Ni=1Nf(pw(xi),yi)\frac1N \sum\limits_{i=1}^N f(p_w(x_i), y_i)

Если представить, что все наши f(pw(xi),yi)f(p_w(x_i), y_i) ― независимые одинаково распределенные случайные величины, то можно считать, что на самом деле мы оптимизируем

1Ni=1Nf(pw(xi),yi)E(x,y)f(pw(x),y)\frac1N \sum\limits_{i=1}^N f(p_w(x_i), y_i) \approx \mathbb{E}_{(x,y)}f(p_w(x), y)

Такую постановку задачи часто называть батчевой (англ. batch). Это означает, что мы можем использовать два класса методов оптимизации:

  • методы, которые на каждом шаге смотрят сразу на всю выборку (например, градиентный спуск или метод Ньютона);
  • методы, которые на каждом шаге смотрят на случайное подмножество данных в надежде, что, итерируясь по таким подмножествам, мы сможем соптимизировать матожидание Ef(w)\mathbb{E}f(w) (например, SGD). Такие методы называют стохастическими.

Существует специальный класс методов анализа сходимости, называемый online to batch conversion. Они позволяют адаптировать алгоритм онлайн-обучения к постановке задачи стохастической оптимизации на фиксированном датасете; при этом оценка на regret транслируется в асимптотику сходимости стохастической оптимизации. Математически строгий вывод этих методов обычно довольно громоздкий и не дарит более глубокого понимания идей в современных стохастических методах, это чисто технические выкладки, поэтому мы здесь ограничимся интуитивным описанием. Строгий вывод можно найти, например, в упомянутой выше книге Shai Shalev-Schwartz.

Процесс стохастической оптимизации на фиксированном датасете можно представить в виде задачи онлайн обучения, если вытянуть все эпохи (проходы по датасетам) в единую последовательность. Мы получим задачу онлайн обучения, в которой (xt,yt)(x_t, y_t) сэмплируются из фиксированного множества (x1,y1),,(xN,yN)(x_1,y_1),\ldots,(x_N,y_N). Строго говоря, тут сэмлпирование двухстадийное:

  1. Берем исходное множество функций
  2. Сэмплируем из него без возвращения, пока множество не станет пустым
  3. Как только оно стало пустым ― заново заполняем его

Таким образом, деление на "эпохи" отчетливо видно и в вытянутой последовательности.

Легко видеть, что эта задача является корректной задачей онлайн обучения. Тут мы активно пользуемся тем, что постановка задачи онлайн обучения математически простая и очень общая. Из корректности данной задачи следует, что все алгоритмы онлайн обучения будут иметь на такой последовательности сублинейный regret.

Следующим шагом давайте взглянем на regret в момент смены эпохи. Обозначим за MM―число эпох, тогда:

maxRegret(T)=maxhH[t=1Tl(pt,yt)t=1Tl(h(xt),yt)]=maxhH[m=1Mi=1Nl(pm,i,yi)m=1Mi=1Nl(h(xi),yi)]=maxhH[m=1Mi=1Nl(pm,i,yi)Mi=1Nl(h(xi),yi)]maxRegret(T) = \max\limits_{h^* \in H}\left[ \sum\limits_{t=1}^T l(p_t, y_t) - \sum\limits_{t=1}^Tl(h^*(x_t), y_t)\right] = \max\limits_{h^* \in H}\left[ \sum\limits_{m=1}^M \sum\limits_{i=1}^N l(p_{m,i}, y_i) - \sum\limits_{m=1}^M \sum\limits_{i=1}^N l(h^*(x_i), y_i)\right] = \max\limits_{h^* \in H}\left[ \sum\limits_{m=1}^M \sum\limits_{i=1}^N l(p_{m,i}, y_i) - M\sum\limits_{i=1}^N l(h^*(x_i), y_i) \right]

Из сходимости последовательности следует сходимость любой ее подпоследовательности, а значит, последовательность regret'ов в моменты смены эпох тоже ведет себя сублинейно:

1MNmaxhH[m=1Mi=1Nl(pm,i,yi)Mi=1Nl(h(xi),yi)]0\frac{1}{MN}\max\limits_{h^* \in H}\left[ \sum\limits_{m=1}^M \sum\limits_{i=1}^N l(p_{m,i}, y_i) - M\sum\limits_{i=1}^N l(h^*(x_i), y_i) \right] \rightarrow 0

maxhH[1MNm=1Mi=1Nl(pm,i,yi)1Ni=1Nl(h(xi),yi)]0\max\limits_{h^* \in H}\left[ \frac{1}{MN}\sum\limits_{m=1}^M \sum\limits_{i=1}^N l(p_{m,i}, y_i) - \frac1N\sum\limits_{i=1}^N l(h^*(x_i), y_i) \right] \rightarrow 0

1MNm=1Mi=1Nl(pm,i,yi)minhH[1Ni=1Nl(h(xi),yi)]0\frac{1}{MN}\sum\limits_{m=1}^M \sum\limits_{i=1}^N l(p_{m,i}, y_i) - \min\limits_{h^* \in H}\left[ \frac1N\sum\limits_{i=1}^N l(h^*(x_i), y_i) \right] \rightarrow 0

Последнее слагаемое уже выглядит практически как постановка задачи стохастической оптимизации на фиксированном датасете! Интуиция на данный момент подсказывает нам, что разрыв между решениями, даваемыми онлайн обучением, и точным решением задачи батч-оптимизации, будет постепенно сокращаться.

В этот момент интуицию можно выключать―остаются только строгие технические выкладки по ссылкам выше.

Выпуклая онлайн-оптимизация

Выпуклая оптимизация играет центральную роль в анализе алгоритмов онлайн-обучения и позволяет получать эффективные алгоритмы. Вот примеры задач, в которых она хорошо работает:

  1. Линейная оптимизация;
  2. Expert Advice problem;
  3. Линейная/логистическая регрессия.

Для задач, возникающих в глубинном обучении, мы поступим согласно рекомендациям ведущих ученых: возьмем теоретически обоснованный алгоритм выпуклой оптимизации, воткнем в нейросеть и помолимся, чтобы он сохранил свои хорошие свойства. С методами первого порядка, как правило, работает (а здесь мы будем рассматривать только такие методы)

Введём в нашу игру предположение о выпуклости, а заодно попробуем сделать вычисления менее громоздкими. Для этого определим упрощённую игру (2):

  1. Выбираем параметрическую модель wtw_t;
  2. Получаем извне выпуклую функцию потерь ft(w)f_t(w);
  3. Считаем ftf_t в точке wtw_t и получаем наш loss ft(wt)f_t(w_t).

Первое упрощение состоит в том, что прогноз hth_t и бейзлайн hth^*_t мы теперь берём не из абстрактного функционального множества HH, а из некоторого параметризованного семейства. Говоря «модель wtw_t», мы имеем в виду «модель, заданная параметрами wtw_t». Скажем, для линейной регрессии это может быть вектор весов и bias. Regret будет записываться следующим образом:

maxRegretT=t=1Tft(wt)t=1Tft(wT)maxRegret_T = \sum\limits_{t=1}^T f_t(w_t) - \sum\limits_{t=1}^T f_t(w_T^*)

Второе упрощение в том, что мы не думаем о признаках xtx_t и таргетах yty_t. Вся эта информация спрятана в определение функции ft(w)f_t(w). Например, для линейной регрессии ft(w)=(xtTwyt)2f_t(w) = (x_t^Tw - y_t)^2. При этом теперь у нас нет частичной информации о текущем раунде игры перед выбором новой модели wtw_t: ведь мы сначала выбираем wtw_t и лишь потом получаем ft(w)f_t(w).

Обратите внимание: если вы попробуете себе представить онлайн алгоритм на практике, то, как правило, частичная информация о функции ft(w)f_t(w) перед выбором wtw_t вам доступна. Например, рассмотрим рекомендательную систему с онлайн-дообучаемой ранжирующей моделью:

  1. Пользователь пришел, мы сразу пошли в базу данных за его историей покупок и получили признаковое описание (возможно частичное) xtx_t;
  2. С учётом этого признакового описания мы выбираем модель wtw_t и с её помощью оцениваем релевантность товаров этому пользователю;
  3. Смотрим, что купил пользователь и купил ли, это даёт нам ft(wt)f_t(w_t).

Тем не менее, в этом параграфе мы будем считать, что частичной информации нет, потому что хотим разрабатывать наиболее общий фреймворк, а не ad-hoc алгоритмы, использующие конкретный вид этой частичной информации. Если даже для какой-то узкой проблемы можно сформулировать специфический алгоритм, учитывающий частичную информацию, с высокой вероятностью он не будет работать значимо лучше стандартного решения. Если знаете контрпримеры ― напишите, добавим сюда для полноты.

Follow the Leader

Предположим, что мы провели tt шагов игры (2) и теперь выбираем модель wt+1w_{t+1} (как условились, без информации о ft+1(w)f_{t+1}(w)). Наиболее естественным выбором будет алгоритм, минимизирующий ошибку на всех предыдущих раундах

wt+1=argminws=1tfs(w)w_{t+1} = arg\min\limits_w \sum\limits_{s=1}^{t}f_s(w)

Такой алгоритм называется Follow The Leader (FTL), потому что мы идем вплотную за наилучшим возможным алгоритмом-бейзлайном в regret (лидером), который учитывает ещё и информацию с (t+1)(t+1)-го шага:

wt+1=argminws=1t+1fs(w)w*_{t+1} = arg\min\limits_w \sum\limits_{s=1}^{\color{#E06A27}{t+1}}f_s(w)

К сожалению, для алгоритма в таком виде есть важные примеры выпуклых задач, когда он не работает. Допустим, наши функции потерь линейны ft(w)=gtTwf_t(w) = g_t^Tw. Вам может показаться, что линейная функция не особенно похожа на функцию потерь, но, забегая вперед, именно такие функции потерь встретятся дальше при изучении градиентных онлайн-алгоритмов (gt=ft(wt)g_t = \nabla f_t(w_t)).

Рассмотрим одномерную задачу ft(w)=gtwtf_t(w) = g_tw_t, gtRg_t \in \mathbb{R}, wt[1;1]w_t \in[-1;1]. Пусть

gt={0.5t=11t%2=01t%2=1g_t = \begin{cases} -0.5 & t=1 \\ 1 & t\%2 = 0 \\ -1 & t\%2 = 1 \end{cases}

Алгоритм FTL выглядит так:

wT+1=argminwt=1Tgtw=argminww(t=1Tgt)w_{T+1} = arg\min\limits_w\sum\limits_{t=1}^T g_tw = arg\min\limits_w w\Big(\sum\limits_{t=1}^T g_t\Big)

Такие осциллирующие суммы коэффициентов будут заставлять FTL выбирать наихудшее возможное решение в каждом раунде. Функция потерь в каждом раунде будет равна 0.50.5, а кумулятивная функция потерь примет вид t=1T0.5=0.5T\sum\limits_{t=1}^T0.5 = 0.5T. При этом кумулятивная функция потерь константного решения w=0w^*=0 будет равна 0. Получаем линейный regret 0.5T0.5T относительно бейзлайна wT=w=0w_T^* = w^* = 0, алгоритм не сходится.

Follow The Regularized Leader

Чтобы стабилизировать алгоритм, мы добавим регуляризаторы, и назовем получившийся алгоритм Follow The Regularized Leader (FTRL):

wT=argminw[t=1Tft(w)+R(w)]w_T = arg\min\limits_w\Big[ \sum\limits_{t=1}^T f_t(w) + R(w)\Big]

Упражнение. Проверьте, что в примере из предыдущего параграфа добавление регуляризатора стабилизирует осцилляцию решения ww.

Добавка R(w)R(w) должна быть выпуклой и неотрицательной. При этом различный выбор R(w)R(w) будет приводить к различным алгоритмам и различным оценкам на regret.

Первое, что приходит в голову ― это L2L_2 регуляризатор R(w)=w22R(w) = \vert\vert w\vert\vert_2^2. Он даёт алгоритм

wT=argminw[t=1Tft(w)+12λw22]w_T = arg\min\limits_w\Big[ \sum\limits_{t=1}^T f_t(w) +\frac{1}{2\lambda}\vert\vert w\vert\vert_2^2\Big]

Adaptive FTRL

Следующая идея―сделать регуляризатор зависящим от данных (то есть от ftf_t) и своим на каждом раунде T:

wT=argminw[t=1Tft(w)+RT(w)]w_T = arg\min\limits_w\Big[ \sum\limits_{t=1}^T f_t(w) + R_T(w)\Big]

Забегая вперед―все современные градиентные алгоритмы Adam, RMSProp, AdaGrad и т.д. попадают в это семейство data-dependent регуляризаторов и работают значительно эффективнее любых алгоритмов с константными регуляризаторами R(w)R(w).

Обратите внимание: регуляризаторы являются частью алгоритма FTRL, они не входят в формулу для regret, которая по-прежнему имеет вид

RegretT(w)=t=1Tft(wt)t=1Tft(w)Regret_T(w^*) = \sum\limits_{t=1}^T f_t(w_t) - \sum\limits_{t=1}^T f_t(w^*)

Таким образом, мы не изменили постановку решаемой нами задачи, изменили лишь метод ее решения.

Обратите внимание: введение регуляризаторов влияет только на онлайн-алгоритм и выбор wtw_t. Бейзлайны wTw_T^* выбираются как и раньше:

wT=argminwt=1Tft(w)w_T^* = arg\min\limits_w \sum\limits_{t=1}^Tf_t(w)

Линеаризация и вычислительно эффективный FTRL

Рассмотрим пример с логистической регрессией ft(w)=log(1+eytwtTxt)f_t(w) = \log(1 + e^{-y_tw_t^Tx_t}) и константным L2L_2 регуляризатором:

t=1Tlog(1+eytwtTxt)+12ηw22minw\sum\limits_{t=1}^T \log(1 + e^{-y_tw_t^Tx_t}) + \frac{1}{2\eta}\vert\vert w\vert\vert_2^2\longrightarrow\min\limits_w

Классический пример использования онлайн логистической регрессии ― предсказание CTR в рекламе. Миллионы запросов в секунду => миллионы решений этой оптимизационной задачи в секунду (если разбивать на батчи ― тысячи, но сути это не меняет). Успех онлайн-алгоритма в таких задачах определяется его вычислительной эффективностью, как по памяти, так и по скорости. Увы, с этим у нашего алгоритма не всё так хорошо:

  • Скорость: аналитически задача не решается => FAIL
  • Память: нужно хранить все предыдущие запросы xtx_t, t1..Tt\in{1..T} => FAIL

Здесь нам на помощь приходит линеаризация задачи. Если фунции ft(w)f_t(w) выпуклые (вниз) и гладкие (на негладкие посмотрим позже), то они удовлетворяют основному свойству выпуклых функций

f(w)f(wt)+[f(wt)]T(wwt)f(w) \geq f(w_t) + [\nabla f(w_t)]^T(w - w_t)

Разложим все функции ft(w)f_t(w) в точках wtw_t:

ft(w)ft(wt)+[f(wt)]T(wwt)f_t(w) \geq f_t(w_t) + [\nabla f(w_t)]^T(w - w_t)

ft(wt)ft(w)[f(wt)]T(wwt)f_t(w_t) - f_t(w) \leq [\nabla f(w_t)]^T(w - w_t)

Просуммируем от 1 до TT

t=1T(ft(wt)ft(w))t=1T([ft(wt)]Twt[ft(wt)]TwT)\sum\limits_{t=1}^T \Big(f_t(w_t) - f_t(w)\Big) \leq \sum\limits_{t=1}^T \Big([\nabla f_t(w_t)]^Tw_t - [\nabla f_t(w_t)]^Tw^T\Big)

Теперь обозначим gt=ft(wt)g_t = \nabla f_t(w_t) и рассмотрим выпуклую линейную задачу онлайн обучения с функцией потерь f~t(w)=gtTw\widetilde{f}_t(w) = g_t^Tw. Regret для нее выглядит как

LinearizedRegretT(w)=t=1TgtTwtt=1TgtTwLinearizedRegret_T(w^*) = \sum\limits_{t=1}^T g_t^Tw_t - \sum\limits_{t=1}^T g_t^Tw^*

Неравенство выше позволяет нам оценить regret исходной задачи через regret линеаризованной:

RegretT(w)LinearizedRegretT(w)Regret_T(w^*) \leq LinearizedRegret_T(w^*)

Минимизируя правую часть неравенства, мы, безусловно, будем минимизировать и левую, так что мы можем выбирать wtw_t алгоритмом, решающим линеаризованную задачу, и получать хорошо сходящийся метод для исходной задачи.

Посмотрим, будет ли линеаризованный алгоритм вычислительно эффективнее. Посмотрим на линеаризацию задачи с data-depedent регуляризатором:

wT=argminw[t=1T[ft(wt)]Tw+RT(w)]w_T = arg\min\limits_w\Big[ \sum\limits_{t=1}^T \nabla [f_t(w_t)]^Tw + R_T(w)\Big]

Линейные задачи имеют аналитическое решение для широкого спектра RT(w)R_T(w). Собственно, это и есть основное, что нужно помнить на практике ― выбирать регуляризатор так, чтобы эта задача решалась аналитически. Мы рассмотрим простейший случай RT(w)=R(w)=12ηw22R_T(w) = R(w) = \frac{1}{2\eta}\vert\vert w\vert\vert_2^2:

wT=argminw[t=1Tft(wt)Tw+12ηw22]w_T = arg\min\limits_w\Big[ \sum\limits_{t=1}^T \nabla f_t(w_t)^Tw + \frac{1}{2\eta}\vert\vert w\vert\vert_2^2\Big]

Справа дифференцируемая функция, так что мы можем найти wTw_T, приравняв к нулю градиент:

wT=ηt=1Tft(wt)=ηzT,w_T = -\eta\sum\limits_{t=1}^T \nabla f_t(w_t) = -\eta z_T,

где zT=t=1Tft(wt)z_T = \sum\limits_{t=1}^T \nabla f_t(w_t) ― это сумма векторов, которую не нужно пересчитывать заново на каждом шаге, а можно инкрементально обновлять. Благодаря этому нам больше не нужно помнить все предыдущие объекты выборки, достаточно хранить лишь некоторую статистику.

Готово, мы построили наш первый вычислительно эффективный алгоритм онлайн обучения! В дальнейшем мы займемся тем, чтобы найти наилучший вычислительно эффективный алгоритм.

Обратите внимание: теперь вы понимете, почему пример с линейной функцией потерь был так важен: линейные функции соответствуют линеаризованному regret. При этом, как мы уже выяснили, без регуляризатора такие линеаризованные задачи нестабильны.

Обратите внимание: если переписать немного формулу для wTw_T, мы получим:

wT=ηt=1Tft(wt)=wT1ηft(wt)w_T = -\eta\sum\limits_{t=1}^T \nabla f_t(w_t) = w_{T-1} - \eta \nabla f_t(w_t)

Таким образом, формулы FTRL c константным регуляризатором эквивалентны формулам обычного стохастического градиентного спуска. Забегая вперед, скажем, что различия в формулах градиентного спуска и FTRL будут только в разделе Composite objective FTRL. В этих отличиях и будет заключаться преимущество FTRL перед привычным SGD.

Обратите внимание: концепции FTRL и gradient descent в литературе часто называют lazy (ленивая) и greedy (жадная) соответственно.

Gradient descent жадный, потому что алгоритм для обновления wt+1w_{t+1} использует только текущий wtw_t и текущий градиент gtg_t. Всё, что было на предыдущих шагах, алгоритм забывает.

FTRL ленивый, потому что алгоритм в явном виде сохраняет всю информацию с начала обучения и рассчитывает wt+1w_{t+1}, исходя из всей истории g1,,gtg_1,\ldots,g_t, и только после этого применяет все регуляризаторы. Подробнее мы расскажем об этом в разделе «Сравнение Composite Objective FTRL-Proximal и Adaptive Gradient Descent».

Субдифференциал и субградиентные методы

Выше мы рассматривали гладкие функции ft(w)f_t(w). Гладкость ― сильное ограничение, и оно на самом деле необязательно, можно ослабить условие, если использовать субградиенты.

Когда мы переходили от исходной задачи к линеаризованной, мы использовали основное свойство гладких выпуклых функций

f(w)f(wt)+[f(wt)]T(wwt),wtf(w) \geq f(w_t) + [\nabla f(w_t)]^T(w - w_t), \quad \forall w_t

Гладкость обеспечивает существование f(wt)\nabla f(w_t) для всех wtw_t. Но нам ведь не нужно, чтобы существовал именно градиент функции. Нам достаточно, чтобы существовал какой-то вектор gtg_t, для которого выполнено неравенство

f(w)f(wt)+gT(wwt)f(w) \geq f(w_t) + g^T(w - w_t)

И в этом помогают следующие два понятия.

Субдифференциалом функции f(w)f(w) в точке wtw_t называется множество

wtf(w)={gtf(w)f(wt)+fT(wwt),w}\partial_{w_t} f(w) = \left\{ g_t \mid f(w) \geq f(w_t) + f^T(w - w_t),\forall w\right\}

Субградиентом функции f(w)f(w) в точке wtw_t называется любой элемент множества f(wt)\partial f(w_t).

Потребуем, чтобы для любой точки был непустой субдифференциал, и дело в шляпе, можно вместо ft(w)\nabla f_t(w) везде подставлять субградиент gtg_t и обобщить все выкладки выше на негладкий случай.

Примеры. Для гладких функций субдифференциал состоит из одной точки: градиента функции, а субградиент равен градиенту. В качестве примера функции с нетривиальным субградиентом рассмотрим функцию f(x)=xf(x) = \vert x \vert, где xx ― скаляр. Субградиент в точке 00 ― это можество

0x={λxαx}\partial_0|x| = \left\{ \lambda\mid |x| \geq \alpha x \right\}

Легко видеть, что 0x\partial_0\vert x\vert ― это отрезок [1,1][-1, 1].

Замечание. На практике субдифференциал используют не так часто. Оптимизационные задачи с популярными негладкими регуляризаторами L1L_1 решают «в лоб», без перехода к субградиентной оценке, например, с помощью проксимальных методов.

Обратите внимание. В литературе очень часто используется термин Online Mirror Descent. Mirror descent ― это оптимизационная процедура вида

wt+1=argminw[12gtTw+λψ(w)+wwt22],w_{t+1} = arg\min\limits_w \left[\vphantom{\frac12}g_t^Tw + \lambda \psi(w) + \vert\vert w-w_t\vert\vert_2^2\right],

в которой ψ\psi ― дополнительный негладкий регуляризатор (например, тот же L1L_1), который мы как раз таки не заменяем на субградиентную оценку, а вместо этого оптимизируем всё «в лоб». Заметьте, что эти формулы идентичны формулам Proximal Gradient Descent. Если у нас нет регуляризатора ψ\psi, то формулы эквивалентны обычному gradient descent.

Как вы увидите дальше, Mirror Descent ― это частный случай общего фреймворка, который мы описываем.

Субградиентные методы оптимизации.

Почти все градиентные методы оптимизации обобщаются на негладкие функции. Модифицируется необходимое и достаточное условие минимума для выпуклых функций: точка ww^* является минимумом, если субдифференциал содержит ноль: 0f(w)0 \in \partial f(w^*). Очевидно, это прямое обобщение условия для гладких функций, где субдифференциал состоит только из градиента функции.

Чтобы добавить в заметки выделенный текст, нажмите Command + E

Пройдите квиз по параграфу

Чтобы закрепить пройденный материал
Предыдущий параграф14.4. Сходимость SGD

Почему он всё-таки сходится

Следующий параграф15.2. Адаптивный FTRL

Вступайте в сообщество хендбука

Здесь можно найти единомышленников, экспертов и просто интересных собеседников. А ещё — получить помощь или поделиться знаниями.